package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 230. 二叉搜索树中第K小的元素
 *
 * 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
 *
 * 限制：
 * 树中的节点数为 n 。
 * 1 <= k <= n <= 104
 * 0 <= Node.val <= 104
 */
public class KthSmallestElementInBST_230 {
    List<Integer> elements = new ArrayList<Integer>();
    public int kthSmallest(TreeNode root, int k) {
        traverse(root);
        return elements.get(k-1);
    }

    // BST 的中序遍历结果是有序的（升序）
    private void traverse(TreeNode root) {
        if (root == null) {
            return;
        }

        traverse(root.left);
        elements.add(root.val);
        traverse(root.right);
    }
}
